#include "vmrp.h"
Replace::Replace(){
	int i;
	//设定总得访问页数,并分配相应的引用页号和淘汰页号记录数组空间
	cout << "Please input page numbers :" ;
	cin >> PageNumber;
	ReferencePage = new int[sizeof(int) * PageNumber];
	EliminatePage = new int[sizeof(int) * PageNumber];
	//输入引用页号序列(页面走向),初始化引用页数组
	cout << "Please input reference page string :";
	for (i = 0; i < PageNumber; i++)
		cin >> ReferencePage[i];//引用页暂存引用数组
	//设定内存实页数(帧数),并分配相应的实页号记录数组空间(页号栈)
	cout << "Please input page frames :";
	cin >> FrameNumber;
	PageFrames = new int[sizeof(int) * FrameNumber];
}
Replace::~Replace(){}
void Replace::InitSpace(const char * MethodName)
{
	int i;
	cout << endl << MethodName << endl;
	FaultNumber=0;
	//引用还未开始,-1 表示无引用页
	for (i = 0; i < PageNumber; i++)
		EliminatePage[i] = -1;
	for(i = 0; i < FrameNumber; i++)
		PageFrames[i] = -1;
}
//分析统计选择的算法对于当前输入的页面走向的性能
void Replace::Report(void){
	//报告淘汰页顺序
	cout << endl << "Eliminate page:";
	for(int i=0; EliminatePage[i]!=-1; i++) cout << EliminatePage[i] << " ";
		//报告缺页数和缺页率
	cout << endl << "Number of page faults = " << FaultNumber << endl;
	cout << setw(6) << setprecision(3) ;
	cout << "Rate of page faults = " << 100*(float)FaultNumber/(float)PageNumber <<"%"<<endl;
}
//最近最旧未用置换算法
void Replace::Lru(void)
{
	int i,j,k,l,next;
	InitSpace("LRU");
	//循环装入引用页
	for(k=0,l=0; k < PageNumber; k++){
		next=ReferencePage[k];
		//检测引用页当前是否已在实存
		for (i=0; i<FrameNumber; i++){
			if(next == PageFrames[i]){
				//引用页已在实存将其调整到页记录栈顶
				next= PageFrames[i];
				for(j=i;j>0;j--) PageFrames[j] = PageFrames[j-1];
				PageFrames[0]=next;
			break;
			}
		}
		if(PageFrames[0] == next){
			//如果引用页已放栈顶,则为不缺页,报告当前内存页号
			for(j=0; j<FrameNumber; j++)
				if(PageFrames[j]>=0) if(PageFrames[i]>=0) cout << PageFrames[j] << " ";
			cout << endl;
			continue; //继续装入下一页
		}
		else
			// 如果引用页还未放栈顶,则为缺页,缺页数加 1
			FaultNumber++;
		//栈底页号记入淘汰页数组中
		EliminatePage[l] = PageFrames[FrameNumber-1];
		//向下压栈
		for(j=FrameNumber-1;j>0;j--) PageFrames[j]= PageFrames[j-1];
		PageFrames[0]=next; //引用页放栈顶
		//报告当前实存中页号
		for(j=0; j<FrameNumber; j++)
			if(PageFrames[j]>=0) cout << PageFrames[j] << " ";
		//报告当前淘汰的页号
		if(EliminatePage[l]>=0)
			cout << "->" << EliminatePage[l++] << endl;
		else
			cout << endl;
	}
	//分析统计选择的算法对于当前引用的页面走向的性能
	Report();
}
//先进先出置换算法
void Replace::Fifo(void){
	int i,j,k,l,next;
	InitSpace("FIFO");
	//循环装入引用页
	for(k=0,j=l=0; k < PageNumber; k++){
		next=ReferencePage[k];
		//如果引用页已在实存中,报告实存页号
		for (i=0; i<FrameNumber; i++) if(next==PageFrames[i]) break;
		if (i<FrameNumber){
			for(i=0; i<FrameNumber; i++) if(PageFrames[i]>=0)cout << PageFrames[i] << " ";
			cout << endl;
			continue; // 继续引用下一页
		}
		//引用页不在实存中,缺页数加 1
		FaultNumber++;
		EliminatePage[l]= PageFrames[j]; //最先入页号记入淘汰页数组
		PageFrames[j]=next; //引用页号放最先入页号处
		j = (j+1)%FrameNumber; //最先入页号循环下移
		//报告当前实存页号和淘汰页号
		for(i=0; i<FrameNumber; i++)
			if(PageFrames[i]>=0) cout << PageFrames[i] << " ";
		if(EliminatePage[l]>=0)
			cout << "->" << EliminatePage[l++] << endl;
		else
			cout << endl;
	}
	//分析统计选择的算法对于当前引用的页面走向的性能
	Report();
}
//未实现的其他页置换算法入口
void Replace::Clock(void)
{
	InitSpace("CLOCK");
	int i,j,k,l,next;
	int * bit=new int[FrameNumber];	//设定标志位
	for(int i=0;i<FrameNumber;i++)	//将所有标志位初始化为0
		bit[i]=0;
	//循环装入引用页
	for(k=0,j=l=0; k < PageNumber; k++){
		next=ReferencePage[k];
		//如果引用页已在实存中,报告实存页号
		for (i=0; i<FrameNumber; i++) if(next==PageFrames[i]){ 
			bit[i]=1;//重新给予二次机会
			break;
		};
		if (i<FrameNumber){
			for(i=0; i<FrameNumber; i++) if(PageFrames[i]>=0) cout << PageFrames[i] << " ";
			if(PageFrames[i]>=0) cout << endl;
			continue; // 继续引用下一页
		}
		//引用页不在实存中,缺页数加 1
		FaultNumber++;
		while(bit[j]){	//当该区机会位为1时
			bit[j]=0;//机会位设置为0
			j=(j+1)%FrameNumber;//移向下一位
		}
		EliminatePage[l]= PageFrames[j]; //将机会位为0的帧淘汰
		PageFrames[j]=next; //引用页号放最先入页号处
		bit[j]=1;//给予新帧二次机会
		j = (j+1)%FrameNumber; //最先入页号循环下移
		//报告当前实存页号和淘汰页号
		for(i=0; i<FrameNumber; i++)
			if(PageFrames[i]>=0) cout << PageFrames[i] << " ";
		if(EliminatePage[l]>=0)
			cout << "->" << EliminatePage[l++] << endl;
		else
			cout << endl;
	}
	//分析统计选择的算法对于当前引用的页面走向的性能
	Report();
}
void Replace::Eclock (void)
{
	InitSpace("ECLOCK");
	int i,j,k,l,next;
	int * dbit=new int[FrameNumber];	//设定标志级别位
	for(int i=0;i<FrameNumber;i++)	//将所有标志位初始化为0，即最可能被替换的
		dbit[i]=0;
	//循环装入引用页
	for(k=0,j=l=0; k < PageNumber; k++){
		next=ReferencePage[k];
		//如果引用页已在实存中,报告实存页号
		for (i=0; i<FrameNumber; i++) 
			if(next==PageFrames[i]){ 
				dbit[i]|=2;//表示为最近刚用过
				break;
			};
		if (i<FrameNumber){
			for(i=0; i<FrameNumber; i++) if(PageFrames[i]>=0) cout << PageFrames[i] << " ";
			cout << endl;
			continue; // 继续引用下一页
		}
		//引用页不在实存中,缺页数加 1
		FaultNumber++;
		int lowest_class=3;//最低级别
		int lowest_id=j;//最低级别id
		for(int temp=0;temp<FrameNumber;temp++){	//至少一个循环才能找到最佳替换选择
			if(dbit[temp]<lowest_class){	//如果发现了比目前级别更低的
				lowest_id=j;//更新id
				lowest_class=dbit[temp];//更新级别数量
			}
			dbit[j]|=0;//重置为最近没有访问过的
			j=(j+1)%FrameNumber;//移向下一位
		}
		j=lowest_id;//赋值最低级别id准备替换
		EliminatePage[l]= PageFrames[j]; //将机会位为0的帧淘汰
		PageFrames[j]=next; //引用页号放最先入页号处
		dbit[j]=3;//给予最高级别
		j = (j+1)%FrameNumber; //最先入页号循环下移
		//报告当前实存页号和淘汰页号
		for(i=0; i<FrameNumber; i++)
			if(PageFrames[i]>=0) cout << PageFrames[i] << " ";
		if(EliminatePage[l]>=0)
			cout << "->" << EliminatePage[l++] << endl;
		else
			cout << endl;
	}
	//分析统计选择的算法对于当前引用的页面走向的性能
	Report();
}
void Replace::Lfu(void)
{
	InitSpace("LFU");
	int k,j,l,next,i;
	int * count=new int[FrameNumber];	//新建一个数组保存次数
	for(i=0;i<FrameNumber;i++)
		count[i]=0;		//初始化为0
	//循环装入引用页
	for(k=0,j=l=0; k < PageNumber; k++){
		next=ReferencePage[k];
		//如果引用页已在实存中,报告实存页号
		for (i=0; i<FrameNumber; i++) 
			if(next==PageFrames[i]){
				count[i]++;//计数增加
				break;
			} 
		if (i<FrameNumber){
			for(i=0; i<FrameNumber; i++) if(PageFrames[i]>=0) cout << PageFrames[i] << " ";
			cout << endl;
			continue; // 继续引用下一页
		}
		//引用页不在实存中,缺页数加 1
		FaultNumber++;
		int l_num=PageNumber;//初始化最少访问次数为最大
		int l_index=0;
		for(int temp=0;temp<FrameNumber;temp++){//遍历所有的计数情况
			if(count[temp]<l_num){	//如果发现了更少的计数
				l_num=count[temp];//更新最少计数
				l_index=temp;//更新索引
			}
		}
		j=l_index;//赋值给预清除页面
		EliminatePage[l]= PageFrames[j]; //加入清除数组
		PageFrames[j]=next; //引用页号放入该页号处
		count[j]=1;//初始化计数为1
		//报告当前实存页号和淘汰页号
		for(i=0; i<FrameNumber; i++)
			if(PageFrames[i]>=0) cout << PageFrames[i] << " ";
		if(EliminatePage[l]>=0)
			cout << "->" << EliminatePage[l++] << endl;
		else
			cout << endl;
	}
	//分析统计选择的算法对于当前引用的页面走向的性能
	Report();
}
void Replace::Mfu(void)
{
	InitSpace("MFU");
	int k,j,l,next,i;
	int * count=new int[FrameNumber];	//新建一个数组保存次数
	for(i=0;i<FrameNumber;i++)
		count[i]=PageNumber;		//初始化为最大情况
	//循环装入引用页
	for(k=0,j=l=0; k < PageNumber; k++){
		next=ReferencePage[k];
		//如果引用页已在实存中,报告实存页号
		for (i=0; i<FrameNumber; i++) 
			if(next==PageFrames[i]){
				count[i]++;//计数增加
				break;
			} 
		if (i<FrameNumber){
			for(i=0; i<FrameNumber; i++) if(PageFrames[i]>=0) cout << PageFrames[i] << " ";
			cout << endl;
			continue; // 继续引用下一页
		}
		//引用页不在实存中,缺页数加 1
		FaultNumber++;
		int m_num=0;//初始化最多访问次数为最小
		int m_index=0;
		for(int temp=0;temp<FrameNumber;temp++){//遍历所有的计数情况
			if(count[temp]>m_num){	//如果发现了更多的计数
				m_num=count[temp];//更新最多计数
				m_index=temp;//更新索引
			}
		}
		j=m_index;//赋值给预清除页面
		EliminatePage[l]= PageFrames[j]; //加入清除数组
		PageFrames[j]=next; //引用页号放入该页号处
		count[j]=1;//初始化计数为1
		//报告当前实存页号和淘汰页号
		for(i=0; i<FrameNumber; i++)
			if(PageFrames[i]>=0) cout << PageFrames[i] << " ";
		if(EliminatePage[l]>=0)
			cout << "->" << EliminatePage[l++] << endl;
		else
			cout << endl;
	}
	//分析统计选择的算法对于当前引用的页面走向的性能
	Report();
}
int main(int argc,char *argv[]){
	Replace * vmpr = new Replace();
	vmpr->Lru();
	vmpr->Fifo();
	vmpr->Clock();
	vmpr->Eclock();
	vmpr->Lfu();
	vmpr->Mfu();
	return 0;
}
